package com.tping.leetcode.array;

import java.util.*;

/**
 * 买卖股票的最佳时机
 *
 * 给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
 *
 * 示例 1：
 * 输入：[7,1,5,3,6,4]
 * 输出：5
 * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
 *
 * 示例 2：
 * 输入：prices = [7,6,4,3,1]
 * 输出：0
 * 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
 *
 * @author xiai
 * @Date 2022/4/12 9:02
 * @Version 1.0
 */
public class Solution_0121 {

    public static void main(String[] args) {
        int[] nums = {7, 1, 5, 3, 6, 4};
        System.out.println("买卖股票的最佳时机的最大利润：" + prices5(nums));
    }

    /**
     * 最大最小值法
     *
     * 算法思路：
     * 利用遍历寻找到合适的位点，分割prices数组
     * 利用一个数据结构帮助我们快速维护一个动态数组的min或max
     *  * 满足栈的特性，先进先出
     *  * 实时维护，push一个元素花费O(1)时间，getMin花费O(1)时间
     *
     * midIndex 移动的过程：
     * a)、左边对应的数组是一个最小栈，不断执行push过程
     * b)、右边对应的数组是一个最大栈，不断执行pop过程
     * c)、最大栈pop的元素正好的最小栈push的元素
     *
     * @param nums
     * @return
     */
    public static int prices5(int[] nums){
        // 最小栈
        Stack<Integer> minStack = new Stack<>();
        minStack.push(nums[0]);

        // 最大栈
        Stack<Integer> maxStack = new Stack<>();
        for (int i = nums.length -1; i > 0; i--) {
            maxStack.push(nums[i]);
        }

        int maxProfit = 0;

        for (int i = 1; i < nums.length; i++) {
            maxProfit = Math.max(getMax(maxStack) - getMin(minStack), maxProfit);
            Integer pop = maxStack.pop();
            minStack.push(pop);
        }

        return maxProfit;
    }

    public static int getMin(Stack<Integer> stack){
        int min = Integer.MAX_VALUE;
        Iterator<Integer> iterator = stack.iterator();
        while (iterator.hasNext()){
            min = Math.min(min, iterator.next());
        }
        return min;
    }

    public static int getMax(Stack<Integer> stack){
        int max = Integer.MIN_VALUE;
        Iterator<Integer> iterator = stack.iterator();
        while (iterator.hasNext()){
            max = Math.max(max, iterator.next());
        }
        return max;
    }


    /**
     * 分治法
     *
     * 算法思路：
     * 原问题的分割：二分方式（price分层price1和price2）
     * 1)、买入卖出日期均在price1中：直接求解prices1
     * 2)、买入卖出日期均在price2中：直接求解prices2
     * 3)、买入日期在prices1中，卖出日期在prices2中：
     *  // 买入日期是prices1中价格最低的那一天
     *  // 卖出日期是prices2中价格最高的那一天
     *
     *  maxProfit = max{prices2} - min{prices1}
     *
     *  子问题解的合并：
     *  递归出口：通常是设定一个常数c，当子问题的输入规模小于等于c时，进行暴力求解，并返回结果
     *  父问题结果合并：三种情况的最大值
     *
     * @param nums
     * @return
     */
    public static int prices4(int[] nums){
        return 0;
    }


    /**
     * 动态规划
     *
     * 算法思路：
     * 假设输入prices的长度为N
     *
     * 第K个子问题：prices中下标范围[0, k-1]
     * 第K个子问题的状态：saleOut[k]; buyIn[k]
     *
     * 动态规划方程：
     *  saleOut[k] = max(prices[k] - buyIn[k - 1], saleOut[k - 1])
     *  buyIn[k] = min(prices[k], buyIn[k- 1])
     *
     * @param nums
     * @return
     */
    public static int price3(int[] nums){
        // 卖出的历史最大利润
        int[] saleOut = new int[nums.length];
        saleOut[0] = 0;

        // 买入的历史最低价格
        int[] buyIn = new int[nums.length];
        buyIn[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            saleOut[i] = Math.max((nums[i] - buyIn[i - 1]), saleOut[i - 1]);
            buyIn[i] = Math.min(nums[i], buyIn[i - 1]);
        }

        return saleOut[saleOut.length - 1];
    }


    /**
     * 贪心法
     * 思路：设第一天的价格为买入价格，当前价格为卖出价格，如果当前卖出的利润小于0，
     * 则设当前价格为买入价格。【算法可以保证，我们会设置“正确卖出价格那一天之前的历史最低价格”为买入价格】
     *
     * 全局最优买入价格，不一定是全局最低价； [10, 90, 5, 80]
     * 全局最优买入价格，不一定是卖出那一天的历史最低价格
     *
     * @param nums
     * @return
     */
    public static int price2(int[] nums){
        // 最大利润
        int maxProfit = 0;
        // 最小价格
        int minPrice = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 当天利润
            int profit = nums[i] - minPrice;
            if( profit > maxProfit ){
                maxProfit = profit;
            }

            // 第二种：判断历史买入价最低
            if( minPrice > nums[i] ){
                minPrice = nums[i];
            }

            // 第一种：若当天利润小于0 ，则当天价格为历史买入价最低
//            if( profit < 0 ){
//                minPrice = nums[i];
//            }
        }

        return maxProfit;
    }

    /**
     * 归约法
     * 思路：price(sale) - price(buy)
     * 最大盈利：从买当天，到卖出时，之间每天日利润之后，累计日利润最大；就是转化为最大子数组和问题
     *
     * 最大子数组和的方式求解
     * 
     * @param nums
     * @return
     */
    public static int price(int[] nums){
        int[] maxPrice = new int[nums.length - 1];
        for (int i = 0; i < maxPrice.length; i++) {
            maxPrice[i] = nums[i + 1] - nums[i];
        }
        
        int maxSum = 0;
        int sum = 0;
        for (int i = 0; i < maxPrice.length; i++) {
            sum += maxPrice[i];
            if( sum > maxSum ){
                maxSum = sum;
            }

            if( sum < 0 ){
                sum = 0;
            }
        }
        
        return Math.max(maxSum, 0);
    }
}
